#pragma once
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <time.h>
#define SetSeed() srand((size_t)time(nullptr))
#define N 20000
using namespace std;

//冒泡排序  时间复杂度:O(N) - O(N^2) 空间复杂度:O(1) 稳定
bool BubleSort(int* arr, int size);
//插入排序	时间复杂度:O(N) - O(N^2) 空间复杂度:O(1) 稳定
bool InsertSort(int* arr, int size);
//希尔排序	时间复杂度:O(N^1.3) - O(N^1.65) 空间复杂度:O(1) 不稳定
bool ShellSort(int* arr, int size);
//选择排序	时间复杂度:O(N^2) 空间复杂度:O(1) 不稳定
bool SelectSort(int* arr, int size);
//快排		时间复杂度:O(N*logN) 空间复杂度:O(logN) 不稳定
bool QuickSort(int* arr, int size);
//归并排序	时间复杂度:O(N*logN) 空间复杂度:O(N) 稳定
bool MergeSort(int* arr, int size);
//堆排序	时间复杂度:O(N*logN) 空间复杂度:O(1) 不稳定
bool HeapSort(int* arr, int size);	//(建堆后使用)	降序用小堆,升序用大堆
///////////////非递归系列//////////////////
//快排非递归
bool QuickSortNonR(int* arr, int size);
//归并排序非递归(不借助栈和队列,使用循环)
bool MergeSortNonR(int* arr, int size);